package arrays_and_matrices;

public class ArrayFind {
    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };

        boolean found1 = find1(nums, 24);
        System.out.println("found1 -> " + (found1 ? "YES" : "NO"));

        boolean found2 = find2(nums, 24);
        System.out.println("found2 -> " + (found2 ? "YES" : "NO"));
    }

    /**
     * 普通遍历的方式 [ 时间复杂度 O(m*n)，空间复杂度 O(1) ]
     * @param nums
     * @param target
     * @return
     */
    public static boolean find1(int[][] nums, int target) {
        if (nums == null || nums.length == 0 || nums[0].length == 0) {
            return false;
        }
        int row = nums.length, col = nums[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (nums[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 顺序遍历的方式 [ 时间复杂度 O(M+N)，空间复杂度 O(1) ]
     *
     * 从右上角开始循环，大于target的肯定在下面，小于target的肯定在左面，每次比较可以减少一行/一列数据 （左下角同理）
     * @param nums
     * @param target
     * @return
     */
    public static boolean find2(int[][] nums, int target) {
        if (nums == null || nums.length == 0 || nums[0].length == 0) {
            return false;
        }
        int row = 0 , col = nums[0].length - 1;
        while (row < nums.length - 1 && col >= 0) {
            if (nums[row][col] > target) {
                col--;
            } else if (nums[row][col] < target) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }
}
